package com.linyaonan.leetcode.medium._106;

import java.util.HashMap;
import java.util.Map;

/**
 * 根据一棵树的中序遍历与后序遍历构造二叉树。
 * <p>
 * 注意:
 * 你可以假设树中没有重复的元素。
 * <p>
 * 例如，给出
 * <p>
 * 中序遍历 inorder = [9,3,15,20,7]
 * 后序遍历 postorder = [9,15,7,20,3]
 * 返回如下的二叉树：
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 *
 * @author: Lin
 * @date: 2020/1/18
 */
public class ConstructBinaryTree {
    Map<Integer, Integer> save;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        save = new HashMap<>();
        // 保存中序遍历值与坐标的关系
        for (int i = 0; i < inorder.length; i++) {
            save.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        // 根节点的值
        if (inEnd < 0 || postEnd < 0 || (postStart > postEnd)) {
            return null;
        }
        int root = postorder[postEnd];
        // 中序遍历根节点的坐标
        Integer inIndex = save.get(root);
        // 中序遍历的左数组坐标为 inStart ~ inIndex-1
        // 中序遍历的右数组的坐标为 inIndex+1 ~ inEnd

        // 后序遍历的左数组为postStart ~ postStart + cha - 1
        // 后序遍历的右数组为postStart + cha ~ postEnd - 1
        TreeNode treeNode = new TreeNode(root);
        int cha = inIndex - inStart;
        treeNode.left = build(inorder, inStart, inIndex-1, postorder, postStart, postStart + cha - 1);
        treeNode.right = build(inorder, inIndex+1, inEnd, postorder, postStart + cha, postEnd - 1);
        return treeNode;
    }

}
